#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define NOPATH 0x7fffffff
#define inf 0x7fffffff
const int maxn = 10005;
int n, m, s;
int dis[maxn], vis[maxn];
struct path
{
    int to;
    int len;
    path(int to, int len) : to(to), len(len){};
};

vector<vector<path>> graph;
int main()
{
    cin >> n >> m >> s;
    fill(dis, dis + maxn, inf);
    graph.resize(n + 1);
    for (int i = 0, u, v, w; i < m; ++i)
    {
        cin >> u >> v >> w;
        graph[u].push_back(path(v, w));
    }
    dis[s] = 0; //源点
    for (int i = 0; i <= n; ++i)
    {
        int u = -1, mindis = inf;
        for (int j = 1; j <= n; ++j)
        {
            if (vis[j] == 0 && dis[j] < mindis)
            {
                mindis = dis[j];
                u = j;
            }
        }
        if (u == -1)
            break;
        vis[u] = 1;
        for (int indx = 0; indx < graph[u].size(); indx++)
        {
            path p = graph[u][indx];
            if (vis[p.to] == 1)
                continue;
            dis[p.to] = min(dis[p.to], dis[u] + p.len);
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << dis[i] << " ";
    return 0;
}